home *** CD-ROM | disk | FTP | other *** search
- From: graham@sees.bangor.ac.uk (Graham A Stephen)
- Newsgroups: alt.books.technical
- Subject: Book Announcement
- Date: 22 Sep 1994 07:57:57 -0500
-
- Lecture Notes Series on Computing
- STRING SEARCHING ALGORITHMS
- by Graham A Stephen (Univ Wales)
-
-
- String searching is a subject of both theoretical and practical
- interest in computer science. This book presents a bibliographic
- overview of the field and an anthology of detailed descriptions of
- the principal algorithms available. The aim is twofold: on the
- one hand, to provide an easy-to-read comparison of the available
- techniques in each area, and on the other, to furnish the reader
- with a reference to in-depth descriptions of the major algorithms.
- Topics covered include methods for finding exact and approximate
- string matches, calculating 'edit' distances between strings,
- finding common sequences and finding the longest repetitions within
- strings. For clarity, all the algorithms are presented in a uniform
- format and notation.
-
- Contents: Introduction; String Matching; String Distance and
- Common Sequences; Suffix Trees; Approximate String Matching;
- Repeated Substrings.
-
- Readership: Computer scientists, software developers and
- computational biologists.
-
- 250pp (approx) Pub date: October 1994
- ISBN 981-02-1829-X US$ 34 / UK pounds 25
-
-
- For further information, please contact the Marketing Department,
- World Scientific Publishing Co Pte Ltd at fax no: (65) 382 5919
- or e-mail address: worldscp@singnet.com.sg
-
- =================================================================
-
- DETAILED CONTENTS
-
- 1 Introduction
-
- 2 String Matching
- 2.1 Overview
- 2.1.1 Brute Force
- 2.1.2 Knuth-Morris-Pratt and Boyer-Moore Approaches
- 2.1.3 Hashing Functions
- 2.1.4 Comparative Performance
- 2.1.5 Popularity
- 2.1.6 Multiple-String Searches
- 2.2 Algorithms in Detail
- 2.2.1 Brute Force
- 2.2.2 Knuth-Morris-Pratt
- 2.2.3 Boyer-Moore
- 2.2.4 Boyer-Moore-Horspool
- 2.2.5 Sunday --- Quick Search, Maximal Shift, and Optimal Mismatch
- 2.2.6 Hume and Sunday --- Tuned Boyer-Moore and Least Cost
- 2.2.7 Harrison
- 2.2.8 Karp-Rabin
- 2.3 Further Reading
-
- 3 String Distance and Common Sequences
- 3.1 Overview
- 3.1.1 String Distance Measures
- 3.1.2 String Distance and Longest Common Subsequence
- 3.1.3 Comparative Performance
- 3.1.4 Related Problems
- 3.2 Algorithms in Detail
- 3.2.1 Wagner-Fischer
- 3.2.2 Hirschberg
- 3.2.3 Hunt-Szymanski
- 3.2.4 Masek-Paterson
- 3.2.5 Ukkonen
- 3.2.6 Heaviest Common Subsequence
- 3.3 Further Reading
-
- 4 Suffix Trees
- 4.1 Overview
- 4.1.1 Suffix Tries
- 4.1.2 From Suffix Trie to Suffix Tree
- 4.2 Algorithms in Detail
- 4.2.1 Brute Force
- 4.2.2 McCreight
- 4.2.3 Ukkonen
- 4.3 Further Reading
-
- 5 Approximate String Matching
- 5.1 Overview
- 5.1.1 String Matching with k Mismatches
- 5.1.2 String Matching with k Differences
- 5.1.3 String Matching with Don't-Cares
- 5.1.4 Application Areas
- 5.1.5 Dedicated Hardware and Parallel Algorithms
- 5.2 Algorithms in Detail
- 5.2.1 Landau-Vishkin k-mismatches
- 5.2.2 Shift-Add
- 5.2.3 Tarhio-Ukkonen k-mismatches
- 5.2.4 Baeza-Yates--Perleberg k-mismatches
- 5.2.5 Dynamic Programming k-differences
- 5.2.6 Landau-Vishkin k-differences
- 5.2.7 Chang-Lawler k-differences
- 5.2.8 Chang-Lampe k-differences
- 5.2.9 Wu-Manber k-differences
- 5.3 Further Reading
-
- 6 Repeated Substrings
- 6.1 Overview
- 6.1.1 Repetitions
- 6.1.2 Longest Repeated Substrings
- 6.2 Algorithms in Detail
- 6.2.1 Brute Force
- 6.2.2 Suffix Trees
-
- A Asymptotic Notation
-
- B String Symbology
-
- C Glossary
-
- D Bibliography
-
- Index
-
-
-
-